package com.example.demo.arithmetic.algorithm.stack;

import com.example.demo.arithmetic.datastructure.stack.ArrayStack;

/**
 * @Description: 栈来计算中缀表达式
 * @Author: LLL
 * @Date: 2020-03-14 15:40
 **/
public class StackCalculateExpression {

    /*
     * 分为数栈 符号栈
     * 1.通过一个索引（idx）遍历表达式
     * 2.是数字 入数栈；
     * 符号，如果栈空，直接入符号栈；
     * 否则，与栈元素优先级比较
     * 如果 小于或等于栈元素，就从数栈pop出两个数值，再从符号栈pop出一个符号，进行运算结果入数栈，然后将当前的操作符入符号栈
     * 如果 大于当前栈元素，直接入符号栈
     * 3.扫描完毕，顺序的从数栈和符号栈pop出相应的数值和符号并运算
     * 4.数栈只有一个数字就是计算结果
     */

    public static void main(String[] args) {
        // 计算的表达式
        String expression = "10+1+1+4*8";
        // 分别创建数栈 符号栈
        ArrayStack numStack = new ArrayStack(10);
        ArrayStack operStack = new ArrayStack(10);
        //
        int index = 0;
        int num1 = 0;
        int num2 = 0;
        int oper = 0;
        int res = 0;
        char ch = ' ';
        String keepNum = "";
        while (true) {
            // 依次得到表达式的每一个字符
            int j = 0;
            ch = expression.substring(index, index + 1).charAt(0);
            if (!operStack.isOper(ch)) { // 不是操作符
                //                char c = expression.substring(index, index + 1).charAt(++j);
                //                StringBuilder sb = new StringBuilder();
                //                sb.append(ch);
                //                while (!operStack.isOper(c)) {
                //                    sb.append(c);
                //                }
                //                numStack.push(Integer.valueOf(sb.toString()));
                keepNum += ch;
                if (index == expression.length() - 1) {
                    numStack.push(Integer.parseInt(keepNum));
                } else {
                    // 判断下一字符是不是数字
                    if (operStack.isOper(expression.substring(index + 1, index + 2).charAt(0))) {
                        numStack.push(Integer.parseInt(keepNum));
                        // keepNum清空
                        keepNum = "";
                    }
                }
            } else { // 是操作符
                if (operStack.isEmpty()) {
                    operStack.push(ch);
                } else if (operStack.priority(ch) <= operStack.priority(operStack.peek())) {
                    num1 = numStack.pop();
                    num2 = numStack.pop();
                    oper = operStack.pop();
                    res = numStack.calc((char) oper, num1, num2);
                    numStack.push(res);
                    operStack.push(ch); // 之前放错了
                } else {
                    operStack.push(ch);
                }
            }
            index++;
            if (index >= expression.length()) {
                break;
            }
        }
        while (true) {
            if (operStack.isEmpty()) {
                break;
            }
            num1 = numStack.pop();
            num2 = numStack.pop();
            oper = operStack.pop();
            res = numStack.calc((char) oper, num1, num2);
            numStack.push(res);
        }
        System.out.printf("表达式%s,结果=%d\n", expression, numStack.pop());
    }

}
